package 数组和链表;


import 抽象数据类型.ListNode;

public class 合并排序好的链表 {
	public static ListNode first=null;
 public static ListNode Merge(ListNode list1,ListNode list2) {
	 	if(list1==null) {
	 		return list2;
	 	}
	 	else if(list2==null) {
	 		return list1;
	 	}
	 
	 	while(list1!=null&&list2!=null) {
	 		if(list1.val<list2.val) {
	 			insert(list1.val);
	 			list1=list1.next;
	 			
	 		}
	 		else {
	 			insert(list2.val);
	 			list2=list2.next;
	 		}
	 	}
	 	while(list1!=null) {
	 		insert(list1.val);
 			list1=list1.next;
	 	}
	 	while(list2!=null) {
	 		insert(list2.val);
 			list2=list2.next;
	 	}
	 	return first;
       
    }
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ListNode node=new ListNode(4);
		node.next=new ListNode(5);
		node.next.next=new ListNode(8);
		
		ListNode node2=new ListNode(3);
		node2.next=new ListNode(6);
		node2.next.next=new ListNode(7);
		
		display(Merge(node,node2));
	}
	private static void display(ListNode node) {
		// TODO Auto-generated method stub
	
			 while(node!=null) {
				
				 System.out.print(node.val+"\t");
				 node=node.next;
			 }
			 System.out.println();
		
		
	}
	public static void insert(int n) {
		ListNode node=new ListNode(n);
		ListNode tmp=first;
		if(first==null)
		{
			first=node;
			
		}
		else
		{
			while(tmp.next!=null)
			{
				

				tmp=tmp.next;
				
				
			}
			
			tmp.next=node;
			
		}
	}

}
